package ljl.alg.jianzhioffer.round3.medium;

public class _14_cuttingRope2 {

    class wo_de_hen_da {
        public int cuttingRope(int n) {
            if (n <= 3) return n - 1;

            long res = 1;
            long last = 1;
            int rem = n % 3;
            while (n >= 3) {
                last = res * 3;
                res = last % 1000000007;
                n -= 3;
            }
            if (rem == 0) return (int)res;
            if (rem == 1) return (int)(last / 3 * 4 % 1000000007);
            return (int) (res * 2 % 1000000007);
        }
    }

    /**
     * 不加以解释的话 路飞的比我的要难理解
     * 1. 最终结果需要取余，中间结果为了防止溢出也得取余
     * 2. 结果得用 long 保存，取余后转为 int，不然 gg
     * */
    class lufei2 {
        public int cuttingRope(int n) {
            if (n <= 3)
                return n - 1;
            int rem = n % 3;
            long res = 1;
            long x = 3;
            for (int times = n / 3 - 1; times > 0 ; times /= 2) {
                if (times % 2 == 1) res = res * x % 1000000007;
                x = x * x % 1000000007;
            }
            if (rem == 0)
                return (int) (res * 3 % 1000000007);
            if (rem == 1)
                return (int) (res * 4 % 1000000007);
            return (int)(res * 6 % 1000000007);
        }
    }

}
